import java.util.List;

/**
 * 120. Triangle 三角形最小路径和
 * https://leetcode.com/problems/triangle/description/
 */
class Triangle {
    /**
     * 方法：动态规划，从下往上计算每个位置的最小路径和
     * 
     * Args:
     *   triangle: 给定的三角形数组，每一行包含该行的数字
     * 
     * Returns:
     *   从顶部到底部的最小路径和
     * 
     * Time: O(n^2), n为三角形的行数
     * 
     * Space: O(n), 使用一维数组存储中间结果
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n + 1];
        for(int i = n - 1; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}